package chazhao;
//题目描述：
//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组
//的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最
//小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的
//最小值为1.
public class 旋转数组 {
    public static void main(String[] args) {
        //题目分析:相当于把一个有序递增数组分为两部分，其中一部分有序，另一部分无序。
        //思路分析：用二分查找，如果中间的数比右边的数大，也就是右边的数较小，那最小值就在右边，否则在左边
        //如果相等，则不能判断，就缩小范围即可。
        int []array=new int[]{6,7,8,9,1,2,3,4,5};
        int left =0;
        int right =array.length-1;
        while(left < right){
            int mid=left+(right-left)/2;
            if(array[mid]>array[right]){
                left=mid+1;
            }
            else if(array[mid]<array[right]){
                right=mid;
            }
            else{
                right--;
            }
        }
        System.out.println("最小值是"+array[left]);
    }
}
